翻訳と辞書 Words near each other ・ ギャップジャンクション ・ ギャップダイナミクス ・ ギャップネクサス ・ ギャップフィラー ・ ギャップ・イヤー ・ ギャップ・コノーズ・キーFC ・ ギャップ・コノーズ・キー・ノーマッズFC ・ ギャップ・ジャンクション ・ ギャップ効果 ・ ギャップ定理 ・ ギャップ定理 (計算複雑性理論) ・ ギャップ期 ・ ギャップ結合 ・ ギャップ結合、細隙結合 ・ ギャッベ ・ ギャッラルブルー ・ ギャッラルホルン ・ ギャッラル橋 ・ ギャツァ ・ ギャツァ県 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ギャップ定理 (計算複雑性理論) ： ミニ英和和英辞書 ギャップ定理 (計算複雑性理論)[ぎゃっぷていり] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 定理 ： [ていり] 　【名詞】 1. theorem　2. proposition ・ 理 ： [り] 　【名詞】 1. reason　 ・ 計 ： [けい] 　 1. (n,n-suf) plan　 ・ 計算 ： [けいさん] 　 1. (n,vs) (1) calculation　2. reckoning　3. count　4. (2) forecast　 ・ 複 ： [ふく] 　 1. (n,pref) double　2. compound　 ・ 複雑 ： [ふくざつ] 　 1. (adj-na,n) complexity　2. complication　 ・ 雑 ： [ざつ] 　 1. (adj-na,n) rough　2. crude　 ・ 理論 ： [りろん] 　【名詞】 1. theory　 ・ 論 ： [ろん] 　【名詞】 1. (1) argument　2. discussion　3. dispute　4. controversy　5. discourse　6. debate　7. (2) theory　8. doctrine　9. (3) essay　10. treatise　1 1. comment ギャップ定理 (計算複雑性理論) ： ウィキペディア日本語版 ギャップ定理 (計算複雑性理論)[ぎゃっぷていり] ギャップ定理（ギャップていり、）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。 これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 $F$ に対して、関数 $t$ を求めて、$t$-制限計算可能な関数の集合と $Ft$-制限計算可能関数の集合が一致するようにできる。 この定理はとによって独立に示された。 == ギャップ定理 == この定理の一般的な形は次のようである： :$\backslash Phi$ を 抽象（ブラム）複雑性測度とする。任意の全域計算可能関数 $g$ で $g(x)\; \backslash geq\; x$ なるものに対して、強単調な全域計算可能関数 $t$ が存在して、$t$ と $g\; \backslash circ\; t$ を制限とする複雑性クラスが同値となる。 この定理は具体的な計算模型について言及することなくブラムの公理だけを用いて証明できる。したがって定理は時間、空間、または他の妥当なあらゆる複雑性の尺度に対して適用できる。 特別な場合として時間複雑性に適用すれば、これはもっと単純に次のように述べられる： :任意の全域計算可能関数 $g:\backslash mathbb\backslash to\backslash mathbb$ で $g(x)\; \backslash geq\; x$ なるものに対して、強単調な時間限定 $T(n)$ が存在して $DTIME(g(T(n)))\; =\; DTIME(T(n))$ が成り立つ。 限定関数 $T(n)$（そしてその計算量）は非常に大きい（さらにはとなりうる) から、ギャップ定理から $\backslash mathcal$ や $\backslash mathcal$ のような低い計算量クラスについて興味のある結果は得られない。またこの定理はやと矛盾しない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ギャップ定理 (計算複雑性理論)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.